InforLorV4, Main, Exploration, bibRecord, 002812

Efficient and accurate computation of upper bounds of approximation errors

Identifieur interne : 002812 ( Main/Exploration ); précédent : 002811; suivant : 002813

Efficient and accurate computation of upper bounds of approximation errors

Auteurs : S. Chevillard [France] ; J. Harrison [États-Unis] ; M. Joldes [France] ; Ch. Lauter [France]

Source :

Theoretical computer science [ 0304-3975 ] ; 2011.

RBID : Pascal:11-0158655

Descripteurs français

Pascal (Inist)
- Informatique théorique, Borne supérieure, Erreur approximation, Evaluation fonction, Fonction mathématique, Approximation polynomiale, Virgule flottante, Implémentation, Fonction élémentaire, Formule quadrature, Quadrature, Preuve, Travail sortie, Fonction transcendante, Erreur relative, Maximum, Estimation erreur, Largeur, Algorithme approximation, Sécurité, Validation, Polynôme, Résultat expérimental, 41A10, 65D32, 41A55, 68Wxx, 68W25.
Wicri :
- topic : Preuve.

English descriptors

KwdEn :
- Approximation algorithm, Approximation error, Computer theory, Elementary function, Error estimation, Experimental result, Floating point, Function evaluation, Implementation, Mathematical function, Maximum, Polynomial, Polynomial approximation, Proof, Quadrature, Quadrature formula, Relative error, Safety, Transcendental function, Upper bound, Validation, Width, Work function.

Abstract

For purposes of actual evaluation, mathematical functions f are commonly replaced by approximation polynomials p. Examples include floating-point implementations of elementary functions, quadrature or more theoretical proof work involving transcendental functions. Replacing f by p induces a relative error ∈ = p/f - 1. In order to ensure the validity of the use of p instead of f, the maximum error, i.e. the supremum norm ⁄∈⁄^I∞ must be safely bounded above over an interval I, whose width is typically of order 1. Numerical algorithms for supremum norms are efficient, but they cannot offer the required safety. Previous validated approaches often require tedious manual intervention. If they are automated, they have several drawbacks, such as the lack of quality guarantees. In this article, a novel, automated supremum norm algorithm on univariate approximation errors ∈ is proposed, achieving an a priori quality on the result. It focuses on the validation step and paves the way for formally certified supremum norms. Key elements are the use of intermediate approximation polynomials with bounded approximation error and a non-negativity test based on a sum-of-squares expression of polynomials. The new algorithm was implemented in the Sollya tool. The article includes experimental results on real-life examples.

Affiliations:

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000158
to stream PascalFrancis, to step Curation: 000843
to stream PascalFrancis, to step Checkpoint: 000134
to stream Main, to step Merge: 002858
to stream Main, to step Curation: 002812

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Efficient and accurate computation of upper bounds of approximation errors</title>
<author><name sortKey="Chevillard, S" sort="Chevillard, S" uniqKey="Chevillard S" first="S." last="Chevillard">S. Chevillard</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA, LORIA, Caramel Project-Team, BP 239</s1>
<s2>54506 Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Harrison, J" sort="Harrison, J" uniqKey="Harrison J" first="J." last="Harrison">J. Harrison</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Intel Corporation, 2111 NE 25th Avenue, M/SJF1-13</s1>
<s2>Hillsboro, OR, 97124</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Hillsboro, OR, 97124</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Joldes, M" sort="Joldes, M" uniqKey="Joldes M" first="M." last="Joldes">M. Joldes</name>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>École Normale Supérieure de Lyon, Université de Lyon, Arénaire, LIP (UMR 5668 CNRS - ENS Lyon - INRIA - UCBL), 46 allée d'Italie</s1>
<s2>69364 Lyon</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
<settlement type="city">Lyon</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lauter, Ch" sort="Lauter, Ch" uniqKey="Lauter C" first="Ch." last="Lauter">Ch. Lauter</name>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Université Pierre et Marie Curie Paris VI (CNRS, UMR 7606, LIP6), 4 place Jussieu</s1>
<s2>75252 Paris</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">11-0158655</idno>
<date when="2011">2011</date>
<idno type="stanalyst">PASCAL 11-0158655 INIST</idno>
<idno type="RBID">Pascal:11-0158655</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000158</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000843</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000134</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000134</idno>
<idno type="wicri:doubleKey">0304-3975:2011:Chevillard S:efficient:and:accurate</idno>
<idno type="wicri:Area/Main/Merge">002858</idno>
<idno type="wicri:Area/Main/Curation">002812</idno>
<idno type="wicri:Area/Main/Exploration">002812</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Efficient and accurate computation of upper bounds of approximation errors</title>
<author><name sortKey="Chevillard, S" sort="Chevillard, S" uniqKey="Chevillard S" first="S." last="Chevillard">S. Chevillard</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA, LORIA, Caramel Project-Team, BP 239</s1>
<s2>54506 Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Harrison, J" sort="Harrison, J" uniqKey="Harrison J" first="J." last="Harrison">J. Harrison</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Intel Corporation, 2111 NE 25th Avenue, M/SJF1-13</s1>
<s2>Hillsboro, OR, 97124</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Hillsboro, OR, 97124</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Joldes, M" sort="Joldes, M" uniqKey="Joldes M" first="M." last="Joldes">M. Joldes</name>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>École Normale Supérieure de Lyon, Université de Lyon, Arénaire, LIP (UMR 5668 CNRS - ENS Lyon - INRIA - UCBL), 46 allée d'Italie</s1>
<s2>69364 Lyon</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
<settlement type="city">Lyon</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lauter, Ch" sort="Lauter, Ch" uniqKey="Lauter C" first="Ch." last="Lauter">Ch. Lauter</name>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Université Pierre et Marie Curie Paris VI (CNRS, UMR 7606, LIP6), 4 place Jussieu</s1>
<s2>75252 Paris</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Approximation algorithm</term>
<term>Approximation error</term>
<term>Computer theory</term>
<term>Elementary function</term>
<term>Error estimation</term>
<term>Experimental result</term>
<term>Floating point</term>
<term>Function evaluation</term>
<term>Implementation</term>
<term>Mathematical function</term>
<term>Maximum</term>
<term>Polynomial</term>
<term>Polynomial approximation</term>
<term>Proof</term>
<term>Quadrature</term>
<term>Quadrature formula</term>
<term>Relative error</term>
<term>Safety</term>
<term>Transcendental function</term>
<term>Upper bound</term>
<term>Validation</term>
<term>Width</term>
<term>Work function</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term>
<term>Borne supérieure</term>
<term>Erreur approximation</term>
<term>Evaluation fonction</term>
<term>Fonction mathématique</term>
<term>Approximation polynomiale</term>
<term>Virgule flottante</term>
<term>Implémentation</term>
<term>Fonction élémentaire</term>
<term>Formule quadrature</term>
<term>Quadrature</term>
<term>Preuve</term>
<term>Travail sortie</term>
<term>Fonction transcendante</term>
<term>Erreur relative</term>
<term>Maximum</term>
<term>Estimation erreur</term>
<term>Largeur</term>
<term>Algorithme approximation</term>
<term>Sécurité</term>
<term>Validation</term>
<term>Polynôme</term>
<term>Résultat expérimental</term>
<term>41A10</term>
<term>65D32</term>
<term>41A55</term>
<term>68Wxx</term>
<term>68W25</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Preuve</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">For purposes of actual evaluation, mathematical functions f are commonly replaced by approximation polynomials p. Examples include floating-point implementations of elementary functions, quadrature or more theoretical proof work involving transcendental functions. Replacing f by p induces a relative error ∈ = p/f - 1. In order to ensure the validity of the use of p instead of f, the maximum error, i.e. the supremum norm ⁄∈⁄<sup>I</sup>
∞ must be safely bounded above over an interval I, whose width is typically of order 1. Numerical algorithms for supremum norms are efficient, but they cannot offer the required safety. Previous validated approaches often require tedious manual intervention. If they are automated, they have several drawbacks, such as the lack of quality guarantees. In this article, a novel, automated supremum norm algorithm on univariate approximation errors ∈ is proposed, achieving an a priori quality on the result. It focuses on the validation step and paves the way for formally certified supremum norms. Key elements are the use of intermediate approximation polynomials with bounded approximation error and a non-negativity test based on a sum-of-squares expression of polynomials. The new algorithm was implemented in the Sollya tool. The article includes experimental results on real-life examples.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Auvergne-Rhône-Alpes</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Rhône-Alpes</li>
<li>Île-de-France</li>
</region>
<settlement><li>Lyon</li>
<li>Paris</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Chevillard, S" sort="Chevillard, S" uniqKey="Chevillard S" first="S." last="Chevillard">S. Chevillard</name>
</region>
<name sortKey="Joldes, M" sort="Joldes, M" uniqKey="Joldes M" first="M." last="Joldes">M. Joldes</name>
<name sortKey="Lauter, Ch" sort="Lauter, Ch" uniqKey="Lauter C" first="Ch." last="Lauter">Ch. Lauter</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Harrison, J" sort="Harrison, J" uniqKey="Harrison J" first="J." last="Harrison">J. Harrison</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002812 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002812 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:11-0158655
   |texte=   Efficient and accurate computation of upper bounds of approximation errors
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Efficient and accurate computation of upper bounds of approximation errors

Efficient and accurate computation of upper bounds of approximation errors

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri